package by2019;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
 * 传入一个数组，判断是否存在三个数，使得a+b+c=0；
 * 
 * 这个程序并没有写完，还存在一些问题
 * 我的思路是一次遍历数组，然后调用twoSum的方法
 * 但是twoSum需要返回一个List<List<Integer>>类型
 * 在threeSum中，需要对每一个twoSum返回的List<Integer>中加入遍历的数组元素
 * 这就是现在程序的卡点，并没有什么难点，只是这个sb程序我写了两三天了
 * 现在卡在这里了，看到这个程序就没有一点写代码的欲望
 * 所以决定先把他搁置在这；
 * 以后如果在看到再补全吧                 
 */
public class 三数之和 {

	public static void main(String[] args) {
		int[] nums = new int[] {-1,2,1,3,0};
		//System.out.println(threeSum(nums));
		System.out.println(twoSum(nums, 1));
		
	}
	
	public static List<List<Integer>> threeSum(int[] nums) {
        List<Integer> list = new ArrayList<Integer>() ;
        List<List<Integer>> reList = new ArrayList<List<Integer>>() ;
        
        for(int i=0;i<nums.length;i++) {
        	reList = twoSum(nums, -nums[i]);
        	if(!reList.isEmpty()) {
        		list.add(nums[i]);
        		System.out.println("往reList中添加： "+list);
        		reList.add(list) ;
                System.out.println("===reList: "+reList);
        		//list.removeAll(list);
        	}
            System.out.println("+++reList: "+reList);
        }

        return reList ;
    }
	
	public static List<List<Integer>> twoSum(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		List<Integer> list = new ArrayList<Integer>() ;
		List<List<Integer>> reList = new ArrayList<List<Integer>>() ;
		
		for(int i=0;i<nums.length;i++) {
			 map.put(nums[i], i);
		}
		for(int i=0;i<nums.length;i++) {
			if(map.containsKey(target-nums[i]) ) {
				if(i==map.get(target-nums[i]))
					continue ;
				list.add(nums[i]);
				list.add(target-nums[i]) ;
				reList.add(list) ;
				map.remove(nums[i]);
				map.remove(target-nums[i]) ;
			}
		}
		System.out.println("towSum返回： "+list);
		return reList ;
	}

}
